module VertexCover where
import Datatype

--------------------------------------------------------------------------
---this module provide the whole algorithm of Kenerlization
---and bound search .
---both Kenerlization and bound search will applyed during each iteration
---ref the method boundsearch
-------------------------------------------------------------------------


--get the set from graph  eg : getset key gragh

getset :: String -> Graph -> [String]
getset k [] = []
getset k ((key, set):g)
           | (k==key) = set
           | otherwise = getset k g

iscontainkey :: String -> Graph -> Bool
iscontainkey  k [] = False
iscontainkey k ((key, set):g)
           | (k==key) = True
           | otherwise = False || (iscontainkey k g )

---remove a v from a set
set_remove :: [String] -> String -> [String ]
set_remove   [] r = []
set_remove  (x:xs) r 
				| (x == r) = set_remove xs r
				| otherwise = x : (set_remove xs r)

remove_set :: [String]->[String]-> [String]
remove_set     y []     = y
remove_set     y (x:xs) = remove_set  (set_remove y x) xs

--is a set Contain v
iscontain :: [String]-> String -> Bool
iscontain  [] r = False
iscontain  (x:xs) r 
             | (x == r) = True || ( iscontain xs r )
             |  otherwise = False || (iscontain xs r) 
 				
--add a v from a set

set_add :: [String] -> String -> [String]
set_add    s a
           | (iscontain s a) =  s
           | not (iscontain s a) = a : s
          
           
---get size of a set  eg:  setSize set -> int
setSize :: [String]->Int
setSize   []    = 0
setSize  (x:[]) = 1
setSize  (x:xs) = 1 + (setSize xs)

--remove the graph entry associate with key  
--eg : remove_key graph key  the entry contains
--key will be moved 
remove_key :: Graph -> String -> Graph
remove_key  [] r = []
remove_key  ((key, eset):g) r
		| (key == r) = g
		| otherwise = (key, eset): (remove_key g r) 

--remove elements in a set --
--eg: remove_elem set e
-- e will be remove from set 
remove_elem :: [String]->String->[String]
remove_elem [] r = []
remove_elem (x:xs) r
				| (x==r) = remove_elem xs r
				| otherwise = x : (remove_elem xs r)
				


--remove a vertex from a graph	
--eg : remove_vertex graph  v
-- v's entry will be removed and any entry contains v will also be removed			
remove_vertex :: Graph -> String -> Graph
remove_vertex   [] r = []
remove_vertex  ((key, eset):g) r 
				| (key==r) = remove_vertex g r
				| otherwise = (key, (remove_elem eset r)): remove_vertex g r
				
--remove vertice from a graph
--eg : remove_set_vertex [v1..vn] graph
--all vertex from v1 to vn will be removed from graph
remove_set_vertex :: [String] -> Graph -> Graph
remove_set_vertex	[] g = g
remove_set_vertex   (x:xs) g = remove_set_vertex xs (remove_vertex g x)
				
--find neghbours of a vertex
--eg : find_neghbours v graph 
-- will return v's neghour vertice ,which adjecent with v.
find_neghours :: String -> Graph -> [String]
find_neghours  v [] = []
find_neghours  v ((key, eset):g) 
				|(key == v) = eset
				| otherwise = find_neghours v g


--find a degree one vertex neghbour
find_a_neghbour :: String -> Graph -> String
find_a_neghbour v g 
				| (setSize (getset v g)) == 1  = head (getset v g)
				|  otherwise = error " not degree one vertex "


			



--remove a vertex's neghours from the graph
--eg : remove_neghbours graph v
--remove v's all neghbours from graph. 
remove_neghbours :: Graph -> String -> Graph
remove_neghbours    g r =   remove_set_vertex (find_neghours r g) g


keneprocess :: Graph -> [String] ->[String] -> Int -> Int->String  -> Nodevalue
keneprocess    g  vset cset  k size v
	| (k>=0)&&((setSize (getset v g)) == 0 )&& (iscontainkey v g)  = ( (remove_vertex g v) , (set_remove vset v), cset , k , size-1 )
	| (k>0)&&((setSize (getset v g)) == 1 )&& (iscontainkey v g) = ((remove_neghbours g v), (set_remove vset ( find_a_neghbour v g)), (set_add cset (find_a_neghbour v g )), (k-1) , (size - 1 ) )
	| (k>0)&&((setSize (getset v g)) > k ) && (iscontainkey v g) = ( (remove_vertex g v),  ( set_remove vset v ),(set_add cset  v ), (k-1), (size -1)  )
	| otherwise = ( g, vset, cset, k , size )


applykeneprocess :: Nodevalue -> [String ] -> Nodevalue
applykeneprocess  (g, vset, cset, k, size) []    =  (g, vset, cset , k, size )
applykeneprocess  (g, vset, cset, k, size) (x:xs) 
                            | k>=0 = applykeneprocess (keneprocess g vset cset k size x) xs
                            | otherwise = (g, vset, cset, k, size)


--exhaust apply kenerlization until Node unchange 
runkernalization :: Nodevalue ->  Nodevalue
runkernalization  (g, vset, cset, k, size) 
                  | (k >=0)&&((applykeneprocess (g, vset, cset, k, size) vset ) /= (g, vset , cset ,k,size)) = runkernalization (applykeneprocess (g, vset, cset, k, size) vset) 
                  | otherwise =  (g, vset, cset, k, size)
               

---process bound search tree --


--remove a vertex from a graph for a Nodevalue type--

node_remove_vertex :: Nodevalue ->String -> Nodevalue
node_remove_vertex    (g, vset, cset, k, size)	 v  =( (remove_vertex g v),  (set_remove vset v), (set_add cset v), k-1, size-1 )

--remove a vertex's neighours from a graph for a Nodevalue type--

node_remove_vertex_neghbours :: Nodevalue -> String ->	Nodevalue
node_remove_vertex_neghbours  	(g, vset, cset, k, size) v =( (remove_neghbours g v), (remove_set vset  (find_neghours v g)), cset ++ (find_neghours v g), (k- (setSize (find_neghours v g)) ), ( size- (setSize (find_neghours v g))) )


--bound search tree searching to find vertex cover 

boundsearch :: Nodevalue -> [String]
boundsearch    (g, vset, cset, k, size)
                           |(k >=0) && (size ==0) = cset
                           |(k <=0) && (size > 0) = []
                           |(k <0 ) && (size ==0) = []
                           
boundsearch    node 
               | boundsearch(  process_leftchild (runkernalization node) ) /= [] = boundsearch(  process_leftchild (runkernalization node) )
               | boundsearch(process_rightchild  (runkernalization node) ) /= [] = boundsearch(process_rightchild  (runkernalization node) )
               | otherwise = boundsearch(  process_leftchild (runkernalization node) ) ++ [] ++ boundsearch(process_rightchild  (runkernalization node) ) 


---process left child ---

process_leftchild :: Nodevalue->Nodevalue
process_leftchild     (g, [], cset,k,size )  = (g, [], cset, k, size) 
process_leftchild	 (g, (v:vset), cset, k, size) = runkernalization ( node_remove_vertex    (g, (v:vset), cset, k, size)   v )
---process right child --
process_rightchild :: Nodevalue->Nodevalue
process_rightchild   (g, [] , cset, k, size) = (g, [], cset, k, size) 
process_rightchild   (g, (v:vset), cset, k, size) = runkernalization ( node_remove_vertex_neghbours    (g, (v:vset), cset, k, size)   v )







           
           



        



					